package com.ryujung.linked_list.leetCode_2;
/*
 * @lc app=leetcode.cn id=2 lang=java
 *
 * [2] 两数相加
 */

import com.ryujung.linked_list.node.ListNode;

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * 思路： 循环遍历数组的index，将两个链表的相同位数字相加， 然后根据结果确定是否需要在下次循环中进一位。
 * 
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 是否进位
        boolean isPlusToHigher = false;

        ListNode result = new ListNode(0);
        ListNode curNote = result;
        while (l1 != null || l2 != null || isPlusToHigher) {
            curNote.next = new ListNode(0);
            curNote = curNote.next;
            int val1 = l1 != null ? l1.val : 0;
            int val2 = l2 != null ? l2.val : 0;

            int plusResult = val1 + val2 + (isPlusToHigher ? 1 : 0);
            isPlusToHigher = plusResult > 9;
            curNote.val = isPlusToHigher ? plusResult % 10 : plusResult;

            // 移动指针，判断是否进行下一次循环
            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }
        return result.next;
    }

    /**
     * 2023年01月31日11:47:08追加
     * 思路：
     * 单向链表
     * 将链表的值依次相加，并将进位传递给下一位值，如果没有下一位，就自动补零
     * 方法:
     * 循环判断当前持有的节点是否不为空或存在进位
     * 如果有，则创建新的节点，并将
     */
    public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        int i = 0; // 进位
        ListNode result = null;
        ListNode currentNode = null;

        while (l1 != null || l2 != null || i != 0) {
            ListNode newNode = new ListNode(0);
            if (currentNode != null) {
                currentNode.next = newNode;
            }
            currentNode = newNode;
            int v1 = l1 == null ? 0 : l1.val;
            int v2 = l2 == null ? 0 : l2.val;
            int temp = v1 + v2 + i;
            currentNode.val = temp % 10;
            i = temp / 10;

            if (result == null) {
                result = currentNode;
            }

            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }

        return result;
    }
    // 时间复杂度：O(max(m,n)) 需要遍历两个链表
    // 空间复杂度：o(1) 需要固定数量的临时变量。

}

// @lc code=end
